﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    class SequenceTraversal
    {
        //==============================力扣102 二叉树的层序遍历
        //给你一个二叉树，请你返回其按层序遍历得到的节点值
        //层序遍历即逐层地，从左到右访问所有节点
        public IList<IList<int>> LevelOrder(TreeNode root)
        {
            //借助队列先进先出的的特性，符合一层一层遍历的逻辑，即是图论中的广度优先遍历

            Queue<TreeNode> que = new Queue<TreeNode>();
            if (root != null)
                que.Enqueue(root);
            IList<IList<int>> result = new List<IList<int>>();

            while (que.Count > 0)
            {
                int size = que.Count;
                IList<int> vec = new List<int>();
                for (int i = 0; i < size; i++)
                {
                    TreeNode node = que.Dequeue();
                    vec.Add(node.val);
                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
                result.Add(vec);
            }

            return result;
        }

        //==============================力扣107 二叉树的层序遍历2
        //给你一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
        public IList<IList<int>> LevelOrderBottom(TreeNode root)
        {
            //思路：跟从根节点到叶子节点的遍历一样，最后将结果反转一下

            //借助队列先进先出的的特性，符合一层一层遍历的逻辑，即是图论中的广度优先遍历

            Queue<TreeNode> que = new Queue<TreeNode>();
            if (root != null)
                que.Enqueue(root);
            List<IList<int>> result = new List<IList<int>>();

            while (que.Count > 0)
            {
                int size = que.Count;
                IList<int> vec = new List<int>();
                for (int i = 0; i < size; i++)
                {
                    TreeNode node = que.Dequeue();
                    vec.Add(node.val);
                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
                result.Add(vec);
            }
            result.Reverse();
            return result;
        }

        //=================================力扣199 二叉树的右视图
        //给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值
        public IList<int> RightSideView(TreeNode root)
        {//思路：层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组，随后返回result即可

            Queue<TreeNode> que = new Queue<TreeNode>();
            IList<int> result = new List<int>();

            if (root != null)
                que.Enqueue(root);
            while(que.Count > 0)
            {
                int size = que.Count;
                for(int i =0;i<size; i++)
                {
                    TreeNode node = que.Dequeue();
                    if (i == size - 1)
                        result.Add(node.val);
                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
            }
            return result;
        }

        //===============================力扣637 二叉树的层平均数
        //给定一个非空二叉树，返回一个由每层节点平均值组成的数组
        public IList<double> AverageOfLevels(TreeNode root)
        {//思路：本题就是层序遍历的时候把一层求个总和再取平均值

            Queue<TreeNode> que = new Queue<TreeNode>();
            IList<double> result = new List<double>();

            if (root != null)
                que.Enqueue(root);
            while(que.Count > 0)
            {
                int size = que.Count;
                double all = 0;
                for(int i = 0;i<size;i++)
                {
                    TreeNode node = que.Dequeue();
                    all += node.val;
                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
                result.Add(all / size);
            }
            return result;
        }

        //========================力扣429 N叉树的层序遍历
        //给定一个N叉树，返回其节点值的层序遍历（即从左往右，逐层遍历）
        public IList<IList<int>> LevelOrder(TreeNodeN root)
        {
            Queue<TreeNodeN> que = new Queue<TreeNodeN>();
            IList<IList<int>> result = new List<IList<int>>();

            if (root != null)
                que.Enqueue(root);

            while(que.Count>0)
            {
                int size = que.Count;
                List<int> total = new List<int>();
                for(int i = 0;i<size;i++)
                {
                    TreeNodeN node = que.Dequeue();
                    for(int j = 0;j<node.children.Count;j++)
                    {
                        if(node.children[j] != null)
                            que.Enqueue(node.children[j]);
                    }
                    total.Add(node.val);
                }
                result.Add(total);
            }
            return result;
        }

        //===================================力扣515 在每个树行中找最大值
        //给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
        public IList<int> LargestValues(TreeNode root)
        {
            Queue<TreeNode> que = new Queue<TreeNode>();
            IList<int> result = new List<int>();

            if (root != null)
                que.Enqueue(root);

            while(que.Count>0)
            {
                int size = que.Count;
                int MaxNum = int.MinValue;
                for(int i = 0;i<size;i++)
                {
                    TreeNode node = que.Dequeue();
                    MaxNum = Math.Max(node.val, MaxNum);
                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
                result.Add(MaxNum);
            }
            return result;
           
        }

        //===============================力扣116 填充每个节点的下一个右侧节点指针
        //给定一个完美二叉树，其所有也自及诶单都在同一层，每个父节点都有两个子节点
        //填充其节点的next指针，让这个指针指向下一个右侧节点，如果找不到，则设置为null
        public TreeNode Connect(TreeNode root)
        {
            Queue<TreeNode> que = new Queue<TreeNode>();

            if (root != null)
            {
                que.Enqueue(root);
            }

            while(que.Count > 0)
            {
                int size = que.Count;
                TreeNode Lastnode = null;
                TreeNode node = null;
                for ( int i = 0;i< size; i++)
                {
                    if(i == 0)
                    {
                        Lastnode = que.Dequeue();
                        node = Lastnode;
                    }
                    else
                    {
                        node = que.Dequeue();
                        Lastnode.next = node;
                        Lastnode = Lastnode.next;
                    }
                    

                    if (node.left != null)
                        que.Enqueue(node.left);
                    if (node.right != null)
                        que.Enqueue(node.right);
                }
                node.next = null;
            }
            return root;
        }

        //==================================力扣117 填充每个节点的下一个右侧节点指针 II
        //填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
        public TreeNode Connect_2(TreeNode root)
        {//跟上题一毛一样
            return Connect(root);
        }

    }
}
